package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *
 * 2. 算法分析
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q004_子数组最大平均数 {
    // 暴力法  时间复杂度为O(nk) 空间复杂度为O(1)
    public double findMaxAverage1(int[] nums, int k) {
        int n = nums.length;
        if(n == 1) {
            return nums[0];
        }
        int res = 0;
        for(int i = 0; i < k; i++) {
            res += nums[i];
        }
        for(int i = 1; i + k <= n; i++) {
            int temp = 0;
            for(int j = i; j < i + k; j++) {
                temp += nums[j];
            }
            res = Math.max(res,temp);
        }
        return (double) res / k;
    }

    // 暴力法的优化   时间复杂为O(n) 空间复杂度为O(1)

    /**
     * 优化思路：
     *      对于第一种方式我们的想法就是穷举数组中所有的长度为k的连续子串，实际上中间会出现大量的重复计算
     *      假设当前数组的长度为n，连续子数组的长度为k，则此时我们有n-k+1个子数组的情况，则这些子数组的起始
     *      索引为0,1,2,3,...,n-k+1,则第i个子数组的k和为
     *              sum[i] = nums[i] + nums[i+1] + ... + nums[i+k-2] + nums[i+k-1]
     *      第i+1个子数组的k和为
     *              sum[i+1] = nums[i+1] + nums[i+2] + ... + nums[i+k-1] + nums[i+k]
     *      则他们之间的关系为
     *              sum[i] + nums[i] - nums[i+k] = sum[i-1]
     *
     *      所以我们没有必要从头到为就出当前k和，从而时间复杂度降低为O(n)
     * @param nums
     * @param k
     * @return
     */
    public double findMaxAverage2(int[] nums, int k) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int sum = 0; // 初始化为0为起始的前k项和
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int res = sum;
        for (int i = k; i < n; i++) {
            sum = sum + nums[i] - nums[i - k];
            res = Math.max(res,sum);
        }
        return (double) res / k;
    }

    // 滑动窗口  时间复杂度和空间复杂度同2
    public double findMaxAverage3(int[] nums, int k) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int sum = 0;
        for(int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int res = sum;
        int left = 0;
        int right = k;
        while(right < n) {
            sum += nums[right];
            if(right - left == k) {
                sum -= nums[left];
                res = Math.max(res,sum);
                left++;
            }
            right++;
        }
        return (double) res / k;
    }
}
